package _go

/*17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。





示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
*/
//先把电话好像对应的数字对应好
var digitsMaps map[string][]string = map[string][]string{
	"2": []string{"a", "b", "c"},
	"3": []string{"d", "e", "f"},
	"4": []string{"g", "h", "i"},
	"5": []string{"j", "k", "l"},
	"6": []string{"m", "n", "o"},
	"7": []string{"p", "q", "r", "s"},
	"8": []string{"t", "u", "v"},
	"9": []string{"w", "x", "y", "z"},
}

//定义一个全局的结果
var res []string

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	res = []string{}

	dfs(digits, 0, "")
	return res
}

//digits 原始的数字
//index 当前选择的数字是那个
//当前选择的路径
func dfs(digits string, index int, path string) {
	//退出条件
	if len(digits) == index {
		res = append(res, path)
		return
	}

	for _, v := range digitsMaps[string(digits[index])] {
		//选择一个
		path += v
		//下一层
		dfs(digits, index+1, path)
		//回退
		path = path[:len(path)-1]
	}
}
